package q1060_missingElement;

public class Solution {
    /*
    首先思考一个问题：
    如何判断该数组中缺了多少个数？
    例如 4 6 7 这个数组 7 - 4 + 1 = 4 但是 4 6 7 这个数组包含了 3 个数
    所以缺了 4 - 3 = 1个数 所以 我们能用数组的右边界的index来计算当前0 - index这个范围缺了多少个数
     */
    int missing(int idx, int[] nums) {
        return nums[idx] - nums[0] - idx;
    }

    /*
    在能够知道对应范围缺了多少个数的情况下 我们要如何找到缺少的第k个数？
    我们可以考虑不停的增加index 可以得到不同范围内所缺的数的个数
    例如 4 6 8 11 就是 0 1 2 4
    假设我们要找所缺的第3个数 自然就是在缺2个数和缺4个数的中间
    也就是在增加index 直到missing(index - 1) < k <= missing(index)
    此时就能够得到缺的数 为nums[index - 1] + (k - missing(index - 1))
    也就是从nums[index - 1]开始还缺了(k - missing(index - 1))个数

    所以我们可以用一个o(n)的方法就能够解决该问题
    如何简化为一个二分查找就能够完成的问题
    实际上就是设置左右两个边界 来更快的迭代index
     */
    public int missingElement(int[] nums, int k) {
        int n = nums.length;

        if (k > missing(n - 1, nums)) return nums[n - 1] + k - missing(n - 1, nums);

        int left = 0, right = n - 1, pivot;

        while (left != right) {
            pivot = left + (right - left) / 2;

            if (missing(pivot, nums) < k) left = pivot + 1;
            else right = pivot;
        }

        // kth missing number is larger than nums[idx - 1]
        // and smaller than nums[idx]
        return nums[left - 1] + k - missing(left - 1, nums);
    }

}
